package day0227

var str string
var directions = [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
var globalBoard [][]byte

func exist(board [][]byte, word string) bool {
	str = word
	globalBoard = board
	m, n := len(board), len(board[0])
	used := make([][]bool, m)
	for k := 0; k < m; k++ {
		used[k] = make([]bool, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == word[0] {
				if dfs(i, j, 0, used) {
					return true
				}
			}
		}
	}
	return false
}

//深度优先搜索
func dfs(i, j, index int, used [][]bool) bool {
	if index == len(str) {
		return true
	}
	if i < 0 || j < 0 || i == len(globalBoard) || j == len(globalBoard[0]) || used[i][j] {
		return false
	}
	if globalBoard[i][j] != str[index] {
		return false
	}
	used[i][j] = true
	for k := 0; k < len(directions); k++ {
		nextI := directions[k][0] + i
		nextJ := directions[k][1] + j
		if dfs(nextI, nextJ, index+1, used) {
			return true
		}
	}
	used[i][j] = false
	return false
}
